package targetToOffer.sixteenthDay;

/**
 * @author Godc
 * @description
 */
public class VerifyPostorder {
}
class VerifyPostorderSolution {
    public boolean verifyPostorder(int[] postorder) {
        return dfs(0,postorder.length-1,postorder);
    }
    public boolean dfs(int i,int j,int[] postorder){
        if(i>=j) return true;
        int val = postorder[j];
        // 找到第一个比根节点大的数，来划分左右子树
        int p = i;
        int m;
        while(postorder[p]<val) p++;
        m = p;
        // 开始判断右子树的所有值是否小于根节点
        while(postorder[p]>val) p++;
        return p==j&&dfs(i,m-1,postorder)&&dfs(m,j-1,postorder);
    }
}
